A media recommendation service selects a user-specific subset of media objects from the universe of available media objects that the service determines may be enjoyed by the user. The selected media object can be provided to the user through a network to be rendered on a device of the user, such as a mobile device. A media object can be a song, video, animation, document or other media entity. When a user of the system begins a new session, the user can be associated with the subset of the recommended media items corresponding to the user.